package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/4/15
 * @description <a href="https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode74_搜索二维矩阵 {
    /**
     * 采用二分搜索法
     * 首先对matrix按列遍历,定位target在哪一行
     * 然后在目标行上进行二分搜索,查找目标值target
     * <p>
     * 时间复杂度O(M)+O(logN):遍历列+在目标行上二分搜索
     * 空间复杂度O(1)
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        //边界条件校验
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return false;
        }

        int M = matrix.length;
        int N = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[M - 1][N - 1]) {
            return false;
        }

        //对matrix按列遍历,定位target在哪一行
        int m = 0;
        while (m < M) {
            if (target >= matrix[m][0]) {
                if (target <= matrix[m][N - 1]) {
                    break;
                }
                if (m < M - 1 && target < matrix[m + 1][0]) {
                    break;
                }
            }
            m++;
        }

        //在目标行上进行二分搜索,查找目标值target
        int l = 0;
        int r = N - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (matrix[m][mid] == target) {
                return true;
            }
            if (matrix[m][mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        //未找到,返回false
        return false;

    }
}
